112. 路径总和

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

最直接的方法就是利用递归，遍历整棵树：如果当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum 函数，其中 sum 值减去当前节点的权值；如果当前节点是叶子，检查 sum 值是否为 0，也就是是否找到了给定的目标和。

  var hasPathSum = function(node, sum) {
    if(node===null) return false
  
    sum -= node.val
    if(node.left===null && node.right===null){
      return sum===0
    }
    return  hasPathSum(node.left,sum) || hasPathSum(node.right,sum)
  }

方案二: BFS

我们可以用栈将递归转成迭代的形式。深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的 root->leaf 路径是最后被考虑的，这种情况下深度优先搜索和广度优先搜索代价是相通的。

利用深度优先策略访问每个节点，同时更新剩余的目标和。

所以我们从包含根节点的栈开始模拟，剩余目标和为 sum - root.val

然后开始迭代：

• 弹出当前元素，如果当前剩余目标和为 0 并且在叶子节点上返回 True
• 如果剩余和不为零并且还处在非叶子节点上，将当前节点的所有孩子以及对应的剩余和压入栈中。

  var hasPathSum = function(root, sum) {
    if(root===null) return false
    const nodeStack = new Stack()
    const sumStack = new Stack()
    nodeStack.push(root)
    sumStack.push(sum-root.val)
  
    while(!nodeStack.isEmpty()){
      const node = nodeStack.pop()
      const curSum = sumStack.pop()
      if (node.right == null && node.left == null && curSum === 0){
        // 和递归时不同，不能返回curSum===0，这就是递归和迭代的区别
        return true
      }
      if (node.right != null) {
        nodeStack.push(node.right);
        sumStack.push(curSum - node.right.val)
      }
      if (node.left != null) {
        nodeStack.push(node.left);
        sumStack.push(curSum - node.left.val)
      }
    }
    return false
  }